package listbyorder.access101_200.test126;

import java.util.*;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/9 16:02
 */
public class Solution3 {

    // 方法三： 用BFS先记录一下每个字符串的邻居数组
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> ans = new ArrayList<>();
        // 特判： 当list不包含结尾的单词，直接返回空表
        if (!wordList.contains(endWord)) {
            return ans;
        }
        // 采用bfs找出每个字符串的邻居字符串
        HashMap<String, ArrayList<String>> map = bfs(beginWord, endWord, wordList);
        ArrayList<String> path = new ArrayList<>();
        path.add(beginWord);
        dfs(beginWord, endWord, map, path, ans);
        return ans;
    }

    int min = 0;

    private void dfs(String beginWord, String endWord, HashMap<String, ArrayList<String>> map, ArrayList<String> path, List<List<String>> ans) {
        if (beginWord.equals(endWord)) {
            ans.add(new ArrayList<>(path));
            return;
        }
        if (path.size() - 1 == min) {
            return;
        }
        // 得到所有下一层的节点
        ArrayList<String> neighbors = map.getOrDefault(beginWord, new ArrayList<String>());
        for (String neighbor : neighbors) {
            if (path.contains(neighbor)) {
                continue;
            }
            path.add(neighbor);
            dfs(neighbor, endWord, map, path, ans);
            path.remove(path.size() - 1);
        }
    }

    // bfs确定出每个字符串的邻居数组，另外找出最小的深度
    private HashMap<String, ArrayList<String>> bfs(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        HashMap<String, ArrayList<String>> map = new HashMap<>();    // 创建一个hash表
        boolean isFind = false;

        Set<String> dic = new HashSet<>(wordList);
        while (!queue.isEmpty()) {
            int size = queue.size();
            min++;
            for (int i = 0; i < size; i++) {
                String temp = queue.poll();
                ArrayList<String> neighbors = getNeighbors(temp, dic);
                map.put(temp, neighbors);
                for (String neighbor : neighbors) {
                    if (neighbor.equals(endWord)) {
                        isFind = true;
                    }
                    queue.offer(neighbor);
                }
            }
            if (isFind) {
                break;
            }
        }
        return map;
    }

    // 在list中找邻居
    private ArrayList<String> getNeighbors(String node, Set<String> dic) {
        ArrayList<String> res = new ArrayList<String>();
        char chs[] = node.toCharArray();

        for (char ch = 'a'; ch <= 'z'; ch++) {
            for (int i = 0; i < chs.length; i++) {
                if (chs[i] == ch)
                    continue;
                char old_ch = chs[i];
                chs[i] = ch;
                if (dic.contains(String.valueOf(chs))) {
                    res.add(String.valueOf(chs));
                }
                chs[i] = old_ch;
            }

        }
        return res;
    }
}
